import java.util.ArrayList;
import java.util.List;

/**
 * 找最左上角块
 */
public class Leetcode120 {
    public static void main(String[] args) {
        List<List<Integer>> list = List.of(
                List.of(2),
                List.of(3, 4),
                List.of(6, 5, 7),
                List.of(4, 1, 8, 3)
        );

        List<List<Integer>> list1 = List.of(
                List.of(-10)
        );

        System.out.println(minimumTotal(list));
        System.out.println(minimumTotal(list1));
    }

    public static int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }

        if (triangle.size() == 2) {
            return Math.min(triangle.get(0).get(0) + triangle.get(1).get(0), triangle.get(0).get(0) + triangle.get(1).get(1));
        }

        int[][] indexMinTotal = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];
        indexMinTotal[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < triangle.size(); i++) {
            indexMinTotal[i][0] = indexMinTotal[i - 1][0] + triangle.get(i).get(0);
            indexMinTotal[i][triangle.get(i).size() - 1] = indexMinTotal[i - 1][triangle.get(i - 1).size() - 1] + triangle.get(i).get(triangle.get(i).size() - 1);

            for (int j = 1; j < triangle.get(i).size() - 1; j++) {
                indexMinTotal[i][j] = Math.min(indexMinTotal[i - 1][j - 1], indexMinTotal[i - 1][j]) + triangle.get(i).get(j);
            }
        }

        int minimumTotal = Integer.MAX_VALUE;
        for (int i = 0; i < indexMinTotal[indexMinTotal.length - 1].length; i++) {
            minimumTotal = Math.min(indexMinTotal[indexMinTotal.length - 1][i], minimumTotal);
        }

        return minimumTotal;
    }


}
